package com.zwj.interview.堆;

import java.util.PriorityQueue;

/**
 * 请设计一个类型KthLargest，它每次从一个数据流中读取一个数字，
 * 并得出数据流已经读取的数字中第k（k≥1）大的数字。该类型的构造函数有两个参数：一个是整数k，
 * 另一个是包含数据流中最开始数字的整数数组nums（假设数组nums的长度大于k）。该类型还有一个函数add，
 * 用来添加数据流中的新数字并返回数据流中已经读取的数字的第k大数字
 * <p>
 * 例如，当k=3且nums为数组[4，5，8，2]时，调用构造函数创建类型KthLargest的实例之后，第1次调用add函数添加数字3，
 * 此时已经从数据流中读取了数字4、5、8、2和3，第3大的数字是4；第2次调用add函数添加数字5时，则返回第3大的数字5
 */
@Deprecated
public class TopKNumber {

    //JDK的PriorityQueue默认是最小堆
    private PriorityQueue<Integer> minHeap;

    private int size;

    //初始化这个最小堆
    public TopKNumber(int k, int[] nums) {
        size = k;
        minHeap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    /**
     * minHeap是一个最小堆。由于minHeap中最多保存k个数字，因此它的空间复杂度是O（k）。
     * 在函数add中，需要在最小堆中添加、删除一个元素，并返回它的堆顶元素，
     * 因此每次调用函数add的时间复杂度是O（logk）
     * @param val
     * @return
     *
     * 假设数据流中总共有n个数字。这种解法特别适合n远大于k的场景。
     * 当n非常大时，内存可能不能容纳数据流中的所有数字。但使用最小堆之后，
     * 内存中只需要保存k个数字，空间效率非常高
     */
    public int add(int val) {
        if (minHeap.size() < size) {
            minHeap.offer(val);
        } else if (val > minHeap.peek()) {
            //弹出的就是堆顶的元素
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }


    public static void main(String[] args) {
        TopKNumber topKNumber = new TopKNumber(3, new int[]{4, 5, 8, 2});
        System.out.println(topKNumber.add(3));
    }



}
